'''
KMP算法，全称为Knuth-Morris-Pratt算法，是一种用来解决字符串匹配问题的算法。
它的目的是在一个文本串text中查找一个模式串pattern出现的位置，时间复杂度为O(m+n)，其中m和n分别为这两个串的长度。
KMP算法是基于对模式串自身的性质进行匹配的算法，它使用了一个next数组来优化匹配，提高了匹配的效率。
'''

def KMPSearch(pattern,text):
    m = len(pattern) # 模式字符串的长度
    n = len(text)     # 文本字符串的长度

    # 预处理next数组
    next = [0] * m  # 初始化next数组为全0
    j = 0
    for i in range(1,m):  # 从第二个字符开始匹配
        while j > 0 and pattern[j] != pattern[i]:  # 如果不匹配，则回溯
            j = next[j - 1]  ## 回溯到前一个字符的next值
        if pattern[j] == pattern[i]:  # 如果匹配，则将j指向下一个字符
            j += 1
        next[i] = j  # 记录当前字符的next值

    # 在 text中查找pattern
    j = 0  # 初始化模式字符串的指针
    for i in range(n):   # 从文本字符串的第一个字符开始匹配
        while j >0 and pattern[j] != text[i]:   # 如果不匹配，则回溯
            j = next[j -1]   # 回溯到前一个字符的next值
        if pattern[j] == text[i]:  # 如果匹配，则将j指向下一个字符
            j += 1
        if j == m:   # 如果j等于m，则表示已经匹配成功
            return i -m +1   # 返回模式字符串在文本字符串中的起始位置
    return -1  # 如果没有找到，则返回-1

text = "ABCABCABCD"
pattern = "CAB"

pos = KMPSearch(pattern,text)
if pos == 1:
    print("未找到")
else:
    print("找到了")


'''
1. 函数 KMPSearch 将模式和文本作为参数。
2. 然后，它创建一个长度为 m 的下一个数组，即形态的长度。
3. 它使用下一个数组来计算一个值 j，该值将用于比较模式和文本。
4.最后，它将通过将图案中的每个字符与文本中的字符进行比较来搜索文本中的模式。如果找到匹配项，它将返回文本中模式的位置。如果未找到匹配项，它将返回 -1。
'''

# python内置函数实现
import re
text1 = "ABCABCABCD"
pattern1 = "CAB"
print(text1.find(pattern1))
print(re.findall(pattern1,text1))
